package done.normal_001_100;

import com.study.common.TreeNode;
import org.junit.Test;

import java.util.*;

import static com.study.util.LogUtil.info;

/**
 * 94. Binary Tree Inorder Traversal 二叉树的中序遍历
 * <p>
 * 给定一个二叉树，返回它的中序 遍历。
 * <p>
 * 示例1:
 * 输入:
 * 1
 * \
 * 2
 * /
 * 3
 * <p>
 * 输出: [1,3,2]
 * <p>
 * 示例2:
 * 输入:
 * 1
 * /    \
 * 4     2
 * / \   / \
 * 5  6  3   8
 * <p>
 * 输出: [5, 4, 6, 1, 3, 2, 8]
 * <p>
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 * <p>
 * 2019-04-20 9:13 AM
 **/
@SuppressWarnings("all")
public class BinaryTreeInorderTraversal {

    public List<Integer> inorderTraversal(TreeNode root) {
        // 190420 first
        // 190421 second 用了两次，没理解
        // 190422 third 递归的没做出来，迭代的一次成功
        return null;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(1,
                new TreeNode(4,
                        5, 6), new TreeNode(2,
                3, 8));
        info("[5, 4, 6, 1, 3, 2, 8] -> {}", inorderTraversal(root));
    }
}




































/*
// 方法2：迭代
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur!=null || !stack.isEmpty()) {
        if (cur!=null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        }
    }
    return list;
}
*/

/*
// 方法1：递归
List<Integer> l = new ArrayList<Integer>();

public List<Integer> inorderTraversal(TreeNode root) {
    inorder(root);
    return l;
}

private void inorder(TreeNode t){
    if (t==null) {
        return;
    }
    inorder(t.left);
    l.add(t.val);
    inorder(t.right);
}
*/
